1. Field of the Invention
The present invention relates to circuit fabrication. More particularly, it relates to a method for improving the location assignment of circuits during fabrication.
2. Prior Art
The process of assigning circuits to locations in, e.g., a chip, frequently includes a stage where all the circuits have been assigned locations, but the assignments are not optimal from either a wiring or timing perspective. For example, certain nets may be on the critical path, and as a result may have delays that are too large. A determination may then be made as to what sets of motions (i.e., assigning a subset of gates to different locations) decrease the sum of the capacitances of the nets on the critical path, with or without weights for the different nets.
Circuit synthesis has traditionally operated on optimized netlists. These optimizations have included both boolean and electrical optimizations. Placement algorithms, on the other hand, have focused primarily on the spatial domain, such as minimizing the total net length or a weighted average of net lengths. With the emergence of sub-micron technologies, there is a need for synthesis and placement algorithms to work seamlessly across all three domains, i.e., boolean, electrical and spatial.
Generally, physical designs have focused on spatial optimizations where the locations of netlist objects are selected with the goal of optimizing a given parameter, e.g., timing, wireability, etc. Recently, synthesis-like electrical optimizations have been implemented into placement subsystems. These electrical optimizations typically operate on the netlist and primarily use the spatial domain only to estimate wire capacitance/RC using a wire length estimator such as a Steiner estimator. Unfortunately, these optimizations do not make significant changes in the locations of the objects.
In view of the foregoing, there is also a need for placement synthesis algorithms to understand the location domain primarily from two main perspectives: 1) correct modeling of the spatial domain; and 2)optimization along the spatial domain. With respect to the correct modeling of the spatial domain, even if one were to focus on only the electrical and boolean domains, in order for the synthesis optimizations to be useful, they would have to model the interconnection correctly. This modeling requires the spatial information. Current techniques in synthesis for modeling interconnection which, for example, estimate wire capacitances as a function of fanouts, are inaccurate.
Examples of optimization along the spatial domain would be moving and rearranging the placement of circuits so as to improve the quality of the circuit for aspects such as timing and wireability. Synthesis has typically dealt with the two dimensions of boolean and electrical optimizations. Various combinations of algorithms are applied, each optimization creating possibilities for further boolean or electrical optimizations or a combination of both. Examples of boolean optimizations are factoring, redundancy removal, etc., while fanout correction/buffer insertion and sizing are examples of electrical optimizations. In later stages of synthesis (known as timing correction), mostly electrical optimization with some boolean optimizations are applied. With the increase in the capacitance/RC of interconnects with sub-micron technologies, synthesis must now consider the spatial domain, and therefore, optimizations now have to operate in all three domains.
As shown in FIG. 1, the synthesis and physical design are separate aspects of the fabrication. Thus, there is a need for an overall strategy of integrating the physical design and synthesis by creating a common framework in which electrical, boolean and location (spatial) optimizations can be performed simultaneously.